재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다.
어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어지며 배열의 각 원소는 해당 지점의 높이를 표시하는 자연수이다.
물에 잠기지 않는 안전한 영역이라 함은 물에 잠기지 않는 지점들이 위, 아래, 오른쪽 혹은 왼쪽으로 인접해 있으며 그 크기가 최대인 영역을 말한다. (꼭짓점으로만 붙어 있는 두 지점은 인접하지 않는다고 취급한다)
첫째 줄에는 어떤 지역을 나타내는 2차원 배열의 행과 열의 개수를 나타내는 수 N이 입력된다. N은 2 이상 100 이하의 정수이다. 둘째 줄부터 N개의 각 줄에는 2차원 배열의 첫 번째 행부터 N번째 행까지 순서대로 한 행씩 높이 정보가 입력된다. 각 줄에는 각 행의 첫 번째 열부터 N번째 열까지 N개의 높이 정보를 나타내는 자연수가 빈 칸을 사이에 두고 입력된다. 높이는 1이상 100 이하의 정수이다.
첫째 줄에 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 출력한다.
바로 전에 풀었던 섬의 개수와 비슷한 문제입니다.
나누어져 있는 영역의 개수를 구하는 것인데, 이번 문제엔 추가적으로 범위에 따라 영역이 변경되는 조건이 붙었습니다.
이 문제에서 주의해야 할 것은 장마철에 영역을 구하는 것이지만 비가 오지 않았을 때의 영역 수도 포함해서 결과를 구해야 하는 것입니다. (왜일까)
예를 들어서 다음과 같을 때, 결과 값은 0이 아니라 1입니다.
3
1 1 1
1 1 1
1 1 1
비가 아예 안 오면 전체 영역이 다 이어져 있으니 1이고, 비가 높이 1 만큼 오면 0이 됩니다.
하지만 비가 오지 않을 때의 높이도 결과에 포함해서 계산해야 하니 답은 1 입니다.
이 부분을 잊지말고 문제를 풀어보았습니다.
| Method | Return | Description |
|---|---|---|
| solution(int N, int[][] arr) | int | DFS를 호출해 높이 별 안전 영역 수를 비교해 최대 안전 영역 수를 반환합니다. |
| DFS(int h, int N, int[][] arr) | int | DFS를 수행하며, 물에 잠기지 않은 영역의 개수를 구합니다. |
| findRange(int[][] arr) | int[][] | 입력 받은 영역에서 높이 범위를 구합니다. |
| applyFlag(int h, int N, int[][] arr) | boolean[][] | 영역의 높이가 특정 높이 h와 비교한 정보를 반환합니다. (true: h 이하, false: h 초과) |
| settingStack(int h, int N, int[][] arr) | Stack<Position> |
영역의 높이가 특정 높이 h보다 높은 경우 스택에 저장합니다. 후에 해당 스택을 반환합니다. |
저번 문제와 유사하게 풀었습니다.
참고로 Main입니다.
사용 연어: Java 11
| 메모리 | 시간 |
| 69120 KB | 420 ms |
감사합니다.
Text by Chaelin. Photographs by Chaelin, Unsplash.